package two.chapter_4.c4_2;

import two.chapter_1.c1_3.LinkStack;
import two.chapter_1.c1_3.LinkedQueue;
import two.chapter_1.c1_3.Queue;
import two.chapter_1.c1_3.Stack;

public class DepthFirstOrder {

    private boolean marked[];
    private Queue<Integer> preQueue;
    private Queue<Integer> postQueue;
    private Stack<Integer> reversePost;
    public DepthFirstOrder(Digragh g){
        preQueue=new LinkedQueue<>();
        postQueue=new LinkedQueue<>();
        reversePost=new LinkStack<>();
        marked=new boolean[g.v()];
        for (int v=0;v<g.v();v++){
            if (!marked[v])
                dfs(g,v);
        }
    }

    private void dfs(Digragh g, int v) {
        marked[v]=true;
        preQueue.enqueue(v);
        for (int w:g.adj(v)){
            if (!marked[w]){
                dfs(g,w);
            }
        }
        postQueue.enqueue(v);
        reversePost.push(v);
    }

    public Iterable<Integer> pre(){
        return preQueue;
    }
    public Iterable<Integer> post(){
        return postQueue;
    }
    public Iterable<Integer> postReverse(){
        return reversePost;
    }
}
